I ran into exactly this problem too. My connections were all physically stable, and established connections (downloads, VoIP calls, etc) were reliable. But new connections were intermittently flaky, and packet loss was appearing while pinging the router's internal addresses.
A quick look at the RRD graphs showed that I was hovering around the 10k default state limit. So I doubled the state table size (in System / Advanced).
Thanks for the thread. Love those graphs.